//
// Created by 啊汤哥 on 2025/6/22.
//
#include <stdio.h>
#include <stdlib.h>

typedef struct  DNode {
    int data; // 节点数据
    struct DNode *prev, *next ;  // 前指针 后指针
} Dnode, *DLinkList;


// 带头结点的初始话
bool InitDoubleLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prev = NULL;
    L->next = NULL;
    return true;
}

// 插入节点 在p节点插入s
bool InsertNextNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false; // 检查节点 p 和 s 是否为空

    s->next = p->next; // 将新节点 s 的 next 指针指向 p 的下一个节点
    if (p->next != NULL) { // 如果 p 不是尾节点
        p->next->prev = s; // 将 p 的下一个节点的 prev 指针指向新节点 s
    }
    s->prev = p; // 将新节点 s 的 prev 指针指向节点 p
    p->next = s; // 将节点 p 的 next 指针指向新节点 s
    return true; // 插入成功，返回 true
}

// 删除操作
bool DeleteNextNode(DNode *p) {
    if (p == NULL || p->next == NULL) return false; // 检查节点 p 是否为空以及是否有后继节点

    DNode *delNode = p->next; // 获取要删除的节点
    p->next = delNode->next; // 将 p 的 next 指针指向要删除节点的下一个节点
    if (delNode->next != NULL) { // 如果要删除的节点不是尾节点
        delNode->next->prev = p; // 将要删除节点的下一个节点的 prev 指针指向 p
    }
    delete delNode; // 释放要删除节点的内存
    return true; // 删除成功，返回 true
}

// 遍历 -- 后向遍历

void TraverseBackward(Dnode *tail) {
    DNode *cur = tail; // 假设 tail 是链表的尾节点
    while (cur != NULL) {
        // 访问当前节点的数据
        printf("%d ", cur->data);
        //  移动到前一个节点
        cur = cur->prev;
    }
    printf("\n"); // 遍历结束后换行
}

// 遍历 -- 前向遍历
void TraverseForward(DNode *head) {
    DNode *cur= head; // 假设 head 是链表的头节点
    while (cur != NULL) {
        // 访问当前节点的数据
        printf("%d ", cur->data);
        // 移动到下一个节点
        cur = cur->next;
    }
    printf("\n"); // 遍历结束后换行
}

// 遍历 -- 前向遍历(无头结点)
void TraverseForwardNoHead(DNode *firstNode) {
    DNode *cur = firstNode; // 假设 firstNode 是链表的第一个节点
    while (cur != NULL) {
        // 访问当前节点的数据
        printf("%d ", cur->data);
        // 移动到下一个节点
        cur = cur->next;
    }
    printf("\n"); // 遍历结束后换行
}
